Netanyahu dipilih pada 1996 setelah gelombang aksi jihad pejuang Palestin menyerang warga sipil Israel. Shimon Peres-yang didukung di TPS-tak dapat menghentikannya dan kepercayaan publik padanya merosot dengan cepat Pada 3 dan 4 Mac 1996, pejuang Palestin mengadakan 2 serangan aksi jihad yang mematikan dan membunuh 32 warga Israel. Kedua serangan itu ialah katalisator utama dalam kejatuhan Peres, yang akhirnya melenyapkan hak pilih karena ketidakmampuannya menghentikan aksi jihad melawan orang-orang Israel. Tidak seperti Peres, Netanyahu tidak percaya pada ‘jasa baik’ Yasser Arafat dan memelihara kemajuan proses perdamaian terhadap Autonomi Palestin memenuhi kewajibannya-terutama melawan pejuang Palestin. Slogan kempennya ialah "Netanyahu-menjaga Perdamaian".

Sering pemerintahan yang baru mengabaikan yang telah menjadi keputusan pemerintahan sebelumnya. Begitu juga Netanyahu yang berasal dari garis keras Israel ini. Perdamaian yang telah dirintis pendahulunya Yitzhak Rabin dan Shimon Peres diabaikan begitu sahaja. Sebagai contoh, menurut hasil kesepakatan Perjanjian Oslo, pasukan Israel mesti ditarik dari sejumlah daerah pendudukannya. Namun, sehingga beberapa tahun, hal itu tidak direalisasikan akibat pergantian pemerintahan.

Sebagai Perdana Menteri ia berunding dengan Yasser Arafat pada forum Persetujuan Wye, namun banyak pernyataan ia mencuba mematikan banyak kemajuan. Pendekatan Netanyahu untuk perundingan perdamaian terkenal dengan:

Tiada kemajuan dalam perbincangan perdamaian dengan orang-orang Palestin dan Netanyahu gagal mewujudkan langkah yang disetujui atas Persetujuan Oslo. Pada 1996, Netanyahu dan walikota Jerusalem Ehud Olmert memutuskan membuka keluaran Tebing Barat. Ini meletuskan 3 hari pergolakan dari orang-orang Palestin, mengakibatkan lebih dari selusin warga Israel dan ribuan warga Palestina terbunuh.

Walaupun ia berprogram melawan ‘kawasan’, Netanyahu dibenci kebanyakan elit dan media massa yang dikenal dengan sayap kiri Israel. Setelah serentetan skandal yang panjang (termasuk gosip tentang isterinya) dan pengusutan membuka perlawanan padanya dalam tuduhan korupsi, Netanyahu kehilangan dukungan dari publik Israel.

Setelah dikalahkan Ehud Barak pada Pemilu Israel 1999, secara temporer Netanyahu beristirahat dari politik.